package sort_code;

//快速排序，以0索引为基数，确认基数在数组中的位置，基数左边比它小，右边比它大
public class Quick {
    public static void main(String[] args) {
        int[] arr = {4,7,1,2,9,3,10,5,8,6};

        int start = 0;
        int end = arr.length - 1;
        quickSort(arr,start,end);

        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }

    private static void quickSort(int[] arr,int i,int j) {
        int start = i;
        //int start = i+1;
        int end = j;
        if(start > end){
            return;
        }
        int number = arr[i];

        while(start != end){

            while (arr[end] >= number && end > start){
                end--;
            }
            while(arr[start] <= number && start < end){
                start++;
            }
            int tmp = arr[start];
            arr[start] = arr[end];
            arr[end] = tmp;
        }
        //if(arr[start] <arr[i]){
            int tmp = arr[i];
            arr[i] = arr[start];
            arr[start] = tmp;
        //} else {
          //  start = i;
        //}


        //归位后左边的数组
        quickSort(arr,i,start - 1);
        //归位后右边的数组
        quickSort(arr, start + 1, j);
    }
}
